17 Monte Carlo Methods

Randomized algorithms, roughly 2 categories

• Las Vagas algorithms

  • always return precisely correct answer or report failed
  • consume random amount of resources: time or memory

• Monte Carlo algorithms

  • return answers with a random amount of error
  • error amount can typically be reduced by expending more resources
  • fixed computational budget, a Monte Carlo algorithm can provide an approximate answer

• 17.1 Sampling and Monte Carlo Methods
• 17.2 Importance Sampling
• 17.3 Markov Chain Monte Carlo Methods
• 17.4 Gibbs Sampling
• 17.5 The challenge of Mixing between Seperated Modes